package com.formula.datastructure.exam.sort;

import com.formula.datastructure.exercise.queue.LinkQueue;
import com.formula.datastructure.util.DataUtil;

public class BucketSort {

    public Integer[] sort(Integer[] array) {
        for (int i = 1; i < 4; i++) {
            array = bucketSort(array, i);
        }
        return array;
    }

    private Integer[] bucketSort(Integer[] array, int digit) {
        int N = array.length;

        int base = power(digit);

        LinkQueue[] queue = new LinkQueue[10];
        for (int i = 0; i < 10; i++) {
            queue[i] = new LinkQueue();
        }

        for (int i = 0; i < N; i++) {
            int bucketId = (array[i] / base) % 10;
            queue[bucketId].enQueue(array[i]);
        }


        int count = 0;
        for (int i = 0; i < 10; i++) {
            while (!queue[i].isEmpty()) {
                array[count++] = queue[i].deQueue();
            }
        }

        return array;
    }

    private int power(int digit) {
        int power = 1;
        for (int i = 1; i < digit; i++) {
            power = power * 10;
        }
        return power;
    }

    public static void main(String[] args) {
        BucketSort bucket = new BucketSort();

        int size = 20;
        int range = 999;
        Integer[] array = DataUtil.genUniqueArray(size, range);
        DataUtil.printIndex(size);
        DataUtil.printArray(array);
        DataUtil.printArray(bucket.sort(array));
    }
}
